package B刷题.二叉树;

/**
 * @author wei.zhao
 * @description: 98.验证二叉搜索树
 */
public class Code06_IsValidBST {

    private Integer max = null;

    private Boolean result = true;

    /**
     * 方式一：使用递归版本的中序遍历，逐个遍历值，与当前最大值比较大小
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        traversal(root);
        return result;
    }

    public void traversal(TreeNode root) {
        if (root == null || !result) {
            return;
        }
        traversal(root.left);
        if (max == null || root.val > max) {
            max = root.val;
        } else {
            result = false;
        }
        traversal(root.right);
    }

    /**
     * 方式二：二叉树的递归套路
     */
    public boolean isValidBST02(TreeNode root) {
        if (root == null) {
            return true;
        }
        Info info = process(root);
        return info.isS;
    }

    private static Info process(TreeNode node) {
        if (node == null) {
            return new Info(true, null, null);
        }
        Info lInfo = process(node.left);
        Info rInfo = process(node.right);
        if (lInfo.isS && rInfo.isS && (lInfo.max == null || lInfo.max < node.val) && (rInfo.min == null || rInfo.min > node.val)) {
            return new Info(true, lInfo.min == null ? node.val : lInfo.min, rInfo.max == null ? node.val : rInfo.max);
        }
        return new Info(false, null, null);
    }

    private static class Info {
        public boolean isS;
        public Integer min;
        public Integer max;

        public Info(boolean isS, Integer min, Integer max) {
            this.isS = isS;
            this.min = min;
            this.max = max;
        }
    }

}
